<?
require_once('ga.php');

class Sudoku {
	var $codigo;
	var $total;
				
	function Sudoku() {
		$this->total = 0;
		$this->codigo = 	"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0".
							"0 0 0 0 0 0 0 0 0";
							
		$this->codigo = str_replace(" ","",$this->codigo);
		$this->generar();	
	}
	
	public function imprimir() {
		echo($this->codigo.":".strlen($this->codigo)."<br>");
		return false;
		echo strlen($this->codigo);
		echo("<br>");
		for($i=0; $i<9; $i++) {
			for($j=0; $j<9; $j++) {
				echo($this->getPos($j,$i)." ");	
			}
			echo("<br>");
		}
	}
	
	public function generar() {
		for($j=1; $j<=15; $j++) {
			if($this->novacios()<81) {
				do {
					$pos = rand(0,80);				
				} while($this->codigo{$pos}!="0");			
				$y = intval($pos/9);
				$x = $pos % 9;				
				$i  = rand(1,9);				
				if($this->vecesfila($i,$y)==0 || $this->vecescolumna($i,$x)==0) {
					$this->setPos($i,$x,$y);
						echo("Inicial: ".strlen($this->codigo)."<br>");
				}							
			}
		}
	}
	
	public function getPos($x,$y) {		
		$pos = ($y*9)+$x;
		return $this->codigo{$pos};
	}
	
	public function setPos($valor,$x,$y) {
		$pos= ($y*9)+$x;	
		$this->codigo = substr_replace($this->codigo,$valor,$pos,1);
	}
	
	public function novacios() {
		$total=0;
		for($i=0; $i<strlen($this->codigo); $i++) {
			$c = $this->codigo{$i};
			if($c!="0") $total++;	
		}
		return $total;
	}
	
	public function vecesfila($valor, $fila) {
		$total = 0;
		for($i=0; $i<9; $i++) {
			$c = $this->getPos($fila,$i);
			if($c!="0") {
				if($valor==$c) $total++;
			}
		}
		return $total;
	}
	
	
	public function vecescolumna($valor, $columna) {
		$total = 0;
		for($i=0; $i<9; $i++) {
			$c = $this->getPos($i,$columna);
			if($c!="0") {
				if($valor==$c) $total++;	
			}
		}
		return $total;
	}
	
	
	public function vecescuadrante($valor, $cuadrante) {
		$y = intval($cuadrante/3)*3;
		$x = intval($cuadrante % 3)*3;
		$total = 0;
		for($i=$y; $i<($y+3); $i++) {
			for($j=$x; $j<($x+3); $j++) {
				$c = $this->getPos($j,$i);
				if($c!="0") {
					if($c==$valor) $total++;	
				}
			}
		}
		return $total;
	}
			
			
	public function evaluar() {
		$total = 0;
		$fallas =0 ;
		for($j=0; $j<9; $j++) {			
			$sumfila = 0;
			$sumcolumna = 0;
			$pila = array();
			for($i=0; $i<9; $i++) {			
				$valor = $i+1;
				if($this->vecesfila($valor,$j)==1) $total++; else $fallas ++;
				if($this->vecescolumna($valor,$j)==1) $total++; else $fallas++;
				if($this->vecescuadrante($valor,$j)==1) $total++; else $fallas++;
				$sumfila= $sumfila + $this->getPos($i,$j);	
				$sumcolumna = $sumcolumna + $this->getPos($j,$i);
			}
			if($sumfila==45) $total++; else $fallas++;
			if($sumcolumna==45) $total++; else $fallas++;
		}
		return $total + $this->novacios() - $fallas;
	}
	
	public function eliminarfila($valor,$fila) {
		for($i=0; $i<9; $i++) {
			if($this->getPos($i,$fila)==$valor) $this->setPos("0",$i,$fila);				
		}
	}
	
	public function eliminarcolumna($valor,$columna) {
		for($i=0; $i<9; $i++) {
			if($this->getPos($columna,$i)==$valor) $this->setPos("0",$columna,$i);				
		}
	}
	
	public function mutar() {
		for($i=1; $i<=9; $i++) {
			for($j=0; $j<9; $j++) {
				if($this->vecescolumna($i,$j)>1) $this->eliminarcolumna($i,$j);
				if($this->vecesfila($i,$j)>1) $this->eliminarfila($i,$j);
			}
		}
			echo("Inicial: ".strlen($this->codigo)."<br>");
		if($this->novacios()<81) {
			do {
				$pos = rand(0,80);				
			} while($this->codigo{$pos}!="0");
			$y = $pos/9;
			$x = $pos % 9;
			for($i=1; $i<=9; $i++) {
				if($this->vecesfila($i,$y)==0 || $this->vecescolumna($i,$x)==0) {
					$this->setPos($i,$x,$y);
					return true;	
				}			
			}
		}
	}

	
	
}

function debug($x) {
	echo "<pre style='border: 1px solid black'>";
	print_r($x);
	echo '</pre>';
}

//This will be the mutation function. Just increments the property.
function inc(Sudoku $s) {
	return $s->mutar();
}
//This will be the crossover function. Is just the average of all properties.
function avg($a,$b) {
	return round(($a+$b)/2);
}
//This will be the fitness function. Is just the sum of all properties.
function total(Sudoku $obj) {
	$obj->evaluar();
}


$adam = new Sudoku();
$eva = new Sudoku();
$ultimo = 0;
$incremento = 0;
for($i=0; $i<20; $i++) {
	$eva->codigo = $adam->codigo;
	$adam->mutar();
	$e = $eva->evaluar();
	$a = $adam->evaluar();
	if($a<$e) $adam->codigo = $eva->codigo;
	echo("evaluando ".$a."<br>");
		echo("Inicial: ".strlen($adam->codigo)."<br>");
	flush();
	if($a==$e) $incremento++;
	if($incremento>20) {
		echo("algoritmo paralizado $incremento<br>");
	}
};
echo("<br>Incremento: $incremento<br>");
$adam->imprimir();
/*
$eve = new Sudoku();

$ga = new GA();
$ga->population = array($adam,$eve);
debug($ga->population);
$ga->fitness_function = 'total';	//Uses the 'total' function as fitness function
$ga->num_couples = 1;				//4 couples per generation (when possible)
$ga->death_rate = 0;				//No kills per generation
$ga->generations = 100;				//Executes 100 generations
$ga->crossover_functions = 'avg';   //Uses the 'avg' function as crossover function
$ga->mutation_function = 'inc';		//Uses the 'inc' function as mutation function
$ga->mutation_rate = 10;			//10% mutation rate
$ga->evolve();						//Run
debug($ga->population);
debug(GA::select($ga->population,'total',1)); //The best

*/

?>